#include "classical-problems.h"

#include <time.h>

#include <algorithm>
#include <map>
#include <hash_map>

#include "str_utils.h"
#include "mt/randomc.h"

namespace pot {
bool IsPrime(int i) {
  if (2 == i) return true;
  if ((i & 1) == 0) return false; // even number that greater than 2

  // odd number won't have even factors, so test odd factors only
  int n = i >> 1;
  for (int j = 3; j < n; j += 2) {
    if ((i % j) == 0) return false;
  }
  return true;
}

void GenNPrimes(int n) {
  for (int i = 2; n > 0; ++i) {
    if (IsPrime(i)) {
      printf("%d, ", i);
      --n;
    }
  }
}

void GenPrimesUpToN(int n) {
  for (int i = 2; i <= n; ++i) {
    if (IsPrime(i)) {
      printf("%d, ", i);
    }
  }
}

void GenPrimeGreaterThenN(int n) {
  while (!IsPrime(n)) ++n;
  printf("%d\n", n);
}

const int kFrequencyOrder[] = {
  2, 19, 11, 9, 0, 15, 16, 7, 4, 22, 21, 10, 13, 5, 3, 18,
  24, 8, 6, 1, 12, 20, 14, 23, 17, 25
};

void GenPrimesAccordingToLetterFrequency() {
  const int n = 26;
  int A[n];
  for (int i = 2, j = 0; j < n; ++i) {
    if (IsPrime(i)) {  
      A[j++] = i;      
    }
  }
  for (int j = 0; j < n; ++j) {
    printf("%d, ", A[kFrequencyOrder[j]]);
  }
}

// arrange the values in the reverse order of letter frequency
const int kHashVals[] = {
  5, 71, 37, 29, 2, 53, 59, 19, 11, 83, 79, 31, 43, 13, 7, 67, 97, 23, 17, 3, 41,
  73, 47, 89, 61, 101, 103
};

// don't consider word that contains special character, such as '-'
inline int Hash(char c) {
  int k = c - 'a';
  //if (k < 0) return kHashVals[0];
  //else 
  return kHashVals[k];
}

long long Hash(const char *word) {  
  long long val = 1;
  while (*word != '\0') {
    val *= Hash(*word);
    ++word;
  }
  return val;
}

int Hash2(const char *word) {
  int val = 0;
  while (*word != '\0') {
    val += Hash(*word++);
  }
  return val;
}

/*
 * 1. use Hash value as signature, then sort by signature
 * 2. use Hash value as the entry point of a anagram list
 *    the length of Hash Table, is determined by the max Hash value of 
 *    the words
 *    use two pass strategy, or use stastics strategy to determine
 *    max Hash value? discard words whose hash value greater than this maximum
 */

long long MaxHashValue(const char* const *words, int n) {
  long long max_val = 0;
  const char *p = NULL;
  for (int i = 0; i < n; ++i) {
    long long val = Hash(words[i]);
    if (val > max_val) {
      max_val = val;
      p = words[i];
    }
  }
  printf("%s\n", p);
  return max_val;
}

inline int Hash(const char *word, int mask) {
  return Hash(word) & mask;
}

int MaxHashValue2(const char* const *words, int n, int mask) {  
  const char *p = NULL;
  int max_val = 0;
  for (int i = 0; i < n; ++i) {
    int val = Hash(words[i], mask);
    if (val > max_val) {
      max_val = val;
      p = words[i];
    }
  }
  printf("%s\n", p);
  return max_val;
}

double ComputeMemoryDemand(long long max_val) {
  return (max_val / 1024.0 / 1024.0) * 4;
}

static const int kBitPrimes[] = {
  1,
  1,
  3,
  7,
  17,
  31,
  67,
  127,
  257,
  521,
  1031,
  2053,
  4099,
  8191,
  16411,
  32771,
  65537,
  131071,
  262147,
  524287,
  1048583,
  2097169,
  4194319,
  8388617,
  16777259,
  33554467,
  67108879,
  134217757,
  268435459,
  536870923,
  1073741827,
  2147483647
};

typedef std::hash_map<int, int> Table;
void HashTest(const char* const *words, int n) {
  for (int bits = 16; bits < 32; bits += 4) {
    const int mask = kBitPrimes[bits];

    int max_val = MaxHashValue2(words, n, mask);
    printf("%d, memory: %f\n", max_val, ComputeMemoryDemand(max_val));
   
    Table table;
    int n_duplicated = 0;
    for (int j = 0; j < n; ++j) {
      int val = Hash(words[j], mask);
      ++table[val];
    }
    for (Table::const_iterator it = table.begin(); it != table.end(); ++it) {
      if (it->second > 1) {
        ++n_duplicated;
        printf("duplicated: %d\n", it->first);
      }
    }
    printf("bits: %d, n_duplicated: %d\n", bits, n_duplicated);
  }
}

int HashMT(const char *word) {
  CRandomMersenne randmc(0);
  int val = 0;
  while (*word != '\0') {
    randmc.RandomInit(*word);
    val |= randmc.IRandom(0, 0x7fffff);
    ++word;
  }
  return val;
}

void MersenneTest(const char* const *words, int n) {
  int max_val = 0;
  const char *p = NULL;
  for (int i = 0; i < n; ++i) {
    int val = HashMT(words[i]);
    if (val > max_val) {
      max_val = val;
      p = words[i];
    }
  }
  printf("%d, %s\n", max_val, p);
  Table table;  
  for (int i = 0; i < n; ++i) {    
    ++table[HashMT(words[i])];
  }
  int n_duplicated = 0;
  for (Table::const_iterator it = table.begin(); it != table.end(); ++it) {
    if (it->second > 1) ++n_duplicated;
  }
  printf("n_duplicated: %d\n", n_duplicated);  
}

//struct SignedWord {
//  typedef char* SigType;
//
//  SignedWord(const char *word) : word(word), sig(NULL) {
//    int len = strlen(word);
//    sig = new char[len + 1];
//    strcpy(sig, word);
//    std::sort(sig, sig + len);
//  }
//
//  SignedWord() : word(NULL), sig(NULL) { }
//
//  ~SignedWord() { if (NULL != sig) delete[] sig; }
//
//  bool operator<(const SignedWord &w) const {
//    int ret = strcmp(this->sig, w.sig);
//    if (ret < 0) return true;
//    if (ret > 0) return false;
//
//    if (strcmp(this->word, w.word) < 0) return true;
//    return false;
//  }
//
//  static int SigCmp(const SigType sig1, const SigType sig2) {
//    return strcmp(sig1, sig2);
//  }
//
//  char *sig;
//  const char *word;
//private:
//  SignedWord(const SignedWord&);
//  SignedWord &operator=(const SignedWord&);
//};

struct SignedWord {
  typedef long long SigType;
  
  SignedWord() : word(NULL), sig(-1) { }

  SignedWord(const char *word) : word(word), sig(-1) {
    sig = pot::Hash(word);
  }

  bool operator<(const SignedWord &w) const {
    if (this->sig < w.sig) return true;
    if (this->sig > w.sig) return false;
    // this is not needed if don't require anagram to be outputed in order
    //if (strcmp(this->word, w.word) < 0) return true; 
    return false;
  }

  static int SigCmp(const SigType sig1, const SigType sig2) {    
    SigType ret = sig1 - sig2;
    if (ret < 0) return -1;
    if (ret > 0) return 1;
    return 0;
  }

  SigType sig;
  const char *word;
};

template<typename T>
class Anagram {
public:
  Anagram(const char* const *words, int n) : 
      words_(words), n_(n), signed_words_(NULL) {
  }

  ~Anagram() { if (NULL != signed_words_) delete[] signed_words_; }

  void Group();
  void Print() const { this->Output(stdout); }
  void Save(const char *filename) const;
private:
  void Output(FILE *fp) const;
  void MakeSignedWords();

private:
  T *signed_words_;
  const char* const *words_;
  int n_;
};

template<typename T>
void Anagram<T>::MakeSignedWords() {
  signed_words_ = new T[n_];
  for (int i = 0; i < n_; ++i) {
    signed_words_[i] = T(words_[i]);
  }
}

template<typename T>
void Anagram<T>::Group() {
  if (NULL == words_) {
    // no words
    return;
  }
  if (NULL != signed_words_) {
    // already grouped
    return;
  }

  this->MakeSignedWords();  

  std::sort(signed_words_, signed_words_ + n_);
}

template<typename T>
void Anagram<T>::Output(FILE *fp) const {
  if (0 == n_) return;

  typename T::SigType sig = signed_words_[0].sig;
  for (int i = 0; i < n_; ++i) {
    if (T::SigCmp(sig, signed_words_[i].sig) != 0) fprintf(fp, "\n");
    fprintf(fp, "%s ", signed_words_[i].word);
    sig = signed_words_[i].sig;
  }
}

template<typename T>
void Anagram<T>::Save(const char *filename) const {
  FILE *fp = fopen(filename, "w");
  if (NULL == fp) {
    printf("can't open %s\n", filename);
    return;
  }
  this->Output(fp);
  fclose(fp);
}

struct node {
  node() : word(NULL), next(NULL) { }
  node(char *w, node *p) : word(w), next(p) { }

  char *word;
  node *next;
};

typedef std::vector<const char*> WordList;

typedef std::hash_map<long long, WordList> HashWordMap;
typedef std::map<long long, WordList> WordMap;

template<typename T>
class AnagramMap {
public:
  AnagramMap(const char* const *words, int n) : words_(words), n_(n) { }
  void Group() {
    for (int i = 0; i < n_; ++i) {
      map_[pot::Hash(words_[i])].push_back(words_[i]);
    }
  }
  void Save(const char *filename) {
    FILE *fp = fopen(filename, "w");
    if (NULL == fp) {
      printf("can't open %s\n", filename);
      return;
    }
    this->Output(fp);
    fclose(fp);
  }
  void Print() { this->Output(stdout); }

private:
  void Output(FILE *fp) {
    typedef T::value_type::second_type WordListType;
    for (T::const_iterator it = map_.begin(); map_.end() != it; ++it) {      
      for(WordListType::const_iterator w = it->second.begin();
          it->second.end() != w; ++w) {
        fprintf(fp, "%s ", *w);
      }
      fprintf(fp, "\n");
    }
  }

private:  
  T map_;
  const char* const *words_;
  int n_;
};

void ProcessDict() {
  FILE *fp = fopen("dict.txt", "r");
  if (NULL == fp) {    
    return;
  }

  FILE *fp2 = fopen("dict2.txt", "w");
  FILE *fp3 = fopen("dict3.txt", "w");

  char buff[256];
  while (fscanf(fp, "%s", buff) != EOF) {
    pot::ToLower(buff);
    fprintf(fp2, "%s\n", buff);
    if (!pot::ContainsNonLetter(buff))
      fprintf(fp3, "%s\n", buff);
  }

  fclose(fp2);
  fclose(fp3);
  fclose(fp);  
}

template<typename T>
void AnagramTest(T &a, const char *filename) {
  clock_t t0 = clock();
  a.Group();
  a.Save(filename);
  clock_t t1 = clock();
  printf("Ok, %s: time = %f\n", filename, (t1 - t0) / 1000.0);
}

void AnagramTest(int max_n) {  
  char *seq = new char[max_n * 10];
  char **words = new char *[max_n + 1];
  const char *filename = "dict3.txt";
  
  FILE *fp = fopen(filename, "r");
  if (NULL == fp) {
    printf("can't open %s\n", filename);
    return;
  }

  int n = 0;
  words[0] = seq;
  while (n < max_n && fscanf(fp, "%s", words[n]) != EOF) {
    words[n + 1] = pot::skip(words[n], 1);
    ++n;
  }
  fclose(fp);

  /*pot::Anagram<SignedWord> anagram(words, n);
  anagram.Group();
  anagram.Save("anagram1.txt");

  pot::AnagramMap<WordMap> map1(words, n);
  map1.Group();
  map1.Save("anagram2.txt");

  pot::AnagramMap<HashWordMap> map2(words, n);
  map2.Group();
  map2.Save("anagram3.txt");*/
  
  printf("n = %d\n", n);

  pot::AnagramTest(pot::Anagram<SignedWord>(words, n), "anagram1.txt");
  pot::AnagramTest(pot::AnagramMap<WordMap>(words, n), "anagram2.txt");
  pot::AnagramTest(pot::AnagramMap<HashWordMap>(words, n), "anagram3.txt");

  printf("Over!\n");
  //pot::GroupAnagram(words, n);

  //pot::HashTest(words, n);
  //pot::MersenneTest(words, n);

  delete[] seq;
  delete[] words;
  //pot::GenPrimesAccordingToLetterFrequency();
 /* for (int bits = 0; bits < 32; ++bits)
    pot::GenPrimeGreaterThenN((1 << bits) - 1);*/
}

void AnagramTest() {
  const int n = 10000;
  const int ns[] = { n, n * 10, n * 100, n * 1000, n * 10000 };
  for (int i = 0; i < 5; ++i) pot::AnagramTest(ns[i]);
}

} // pot
